//给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。 
//
// 规定水流只能按照上、下、左、右四个方向流动，且只能从高到低或者在同等高度上流动。 
//
// 请找出那些水流既可以流动到“太平洋”，又能流动到“大西洋”的陆地单元的坐标。 
//
// 
//
// 提示： 
//
// 
// 输出坐标的顺序不重要 
// m 和 n 都小于150 
// 
//
// 
//
// 示例： 
//
// 
//
// 
//给定下面的 5x5 矩阵:
//
//  太平洋 ~   ~   ~   ~   ~ 
//       ~  1   2   2   3  (5) *
//       ~  3   2   3  (4) (4) *
//       ~  2   4  (5)  3   1  *
//       ~ (6) (7)  1   4   5  *
//       ~ (5)  1   1   2   4  *
//          *   *   *   *   * 大西洋
//
//返回:
//
//[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (上图中带括号的单元).
// 
//
// 
// Related Topics 深度优先搜索 广度优先搜索 数组 矩阵 
// 👍 314 👎 0

package com.cute.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

public class PacificAtlanticWaterFlow {
    public static void main(String[] args) {
        Solution solution = new PacificAtlanticWaterFlow().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * 换一种思路：水往高处流，找出从边缘能流到的所有点
     * 两部分重合的点就是最终的结果
     * 遍历时从上左，右下分别为入口
     * 能访问到的节点都分别置为true
     */
    class Solution {
        int row;
        int col;
        int[][] directions = {{0,1},{0,-1},{1,0},{-1,0}};
        int[][] matrix;
        public List<List<Integer>> pacificAtlantic(int[][] heights) {
            List<List<Integer>> res = new ArrayList<>();
            row = heights.length;
            if (row == 0) return res;
            col = heights[0].length;
            if (col == 0) return res;
            matrix = heights;
            //这里储存两个大洋分别能够到达的节点
            boolean[][] left = new boolean[row][col];
            boolean[][] right = new boolean[row][col];

            for (int i = 0; i < col ; i++) {
                dfs(0, i, left);//上边界为入口
                dfs(row-1, i, right);//下边界为入口
            }
            for (int i = 0; i < row ; i++) {
                dfs(i, 0, left);//左边界为入口
                dfs(i, col-1, right);//右边界为入口
            }
            for (int i = 0; i < row ; i++) {
                for (int j = 0; j < col ; j++) {
                    if (left[i][j]&&right[i][j]){//左右都能到达的再加入到结果集中去
                        List<Integer> temp = new ArrayList<>();
                        temp.add(i);
                        temp.add(j);
                        res.add(temp);
                    }
                }
            }
            return res;
        }

        public void dfs(int x, int y, boolean[][] reach){
            reach[x][y] = true;//先将当前方向的访问标志置为true
            for (int[] d : directions){
                int newX = x + d[0];
                int newY = y + d[1];
                //如果下一个坐标没有越界，且>=当前坐标处的值，且下一个坐标没有被置为true再递归
                if (inGrid(newX, newY)&& matrix[x][y]<=matrix[newX][newY]&&!reach[newX][newY])
                    dfs(newX, newY, reach);
            }
        }

        public boolean inGrid(int x, int y){
            return x>=0 && x<row && y>=0 && y< col;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
































